#pragma once
#include "../flow/mcmf.hpp"
#include "../IO Interface/DataManager.h"
#include "../flow/flow.hpp"
#include <algorithm>

/*
˼·��
0������cycle�β���1~4
1��Ϊÿһ��site����ÿһ��ʱ�̵Ĺ滮ֵsite_value�����������ʹ�������
2����ĳ��site����site_valueǰ5%���ʱ���������site�ķ��ù���Ϊ0,������ù���Ϊ1��
3�����з��������������Ʒ���Ϊ1����������

����site_value�ļ��㣺
1����ʼʱ��site_value[siteID][time]����min(bandwidthLimit[site],timeʱ��siteID����client������)
2�����ݷ������������site_valueֵ����Ϊ��������С


�����ݲ�ʵ��idea:
��[0%, 95%]��site_value��ĳ���Ż�������С
*/


/* 
planA:
baseline��178238
cycleCnt=1 binaruCnt = infinity: 128162
cycleCnt=2 binaruCnt = infinity: 115423
cycleCnt=3 binaruCnt = infinity: 107078
cycleCnt=4 binaruCnt = infinity: 101634
cycleCnt=5 binaruCnt = infinity: 89483
cycleCnt=6 binaruCnt = infinity: 76938
cycleCnt=7 binaruCnt = infinity: 63349


cycleCnt=1 binaruCnt = 5: 150175
cycleCnt=2 binaruCnt = 5: 125658
cycleCnt=3 binaruCnt = 5: 103471
cycleCnt=4 binaruCnt = 5: 
cycleCnt=5 binaruCnt = 5: 
cycleCnt=6 binaruCnt = 5: 
cycleCnt=7 binaruCnt = 5: 

*/

class OptimizerMcmfPlanA
{
private:
	long long INFINITY_CAPICITY;

	struct Edge
	{
		int u, v, nxt;
	};
	std::vector<Edge> edge;
	std::vector<int> head;
	int cnt;

	DataManager* dataManager;
	MCMF* mcmf;
	Flow* maxFlow;
	int siteNum, timeNum, clientNum;
	std::vector<std::vector<int>> bandwidthDemand;		// time,clientID,��������
	std::vector<int> bandwidthLimit;					// siteID,��������
	std::vector<std::pair<int, int>> graphSiteToClient;	// <siteID, clientID>

	int rank95;
	std::vector<std::vector<int>> siteValue;			//site,time,��������ֵ
	std::vector<int> localSiteValue;					//site, value
	std::vector<std::vector<int>> siteValueSortRank;	//site, rank, ��Ӧ������ʱ��ֵ
	std::vector<int> localSiteValueSortRank;			//rank, site
	std::vector<std::vector<int>> siteValueTimeRank;	//site, time, ��Ӧʱ�������
	std::vector<int> localSiteValueSiteRank;			//site, rank

	std::vector<int> maxSiteBandwidth;					//time, ĳ��site�������

	std::vector<std::vector<std::vector<std::pair<int, int>>>> log;	//time, clientID, <siteID, bandwidth>
	
	std::vector<int> timeTotalDemand;					//time, ���������

	void insert(int u, int v);
	void initSiteValue();								//��ʼ��site_valueֵ
	void setFlowGraph(int limitFlow, int time, int currentCycle);								//����site_valueֵ���������
	void updateSiteValue();								//���÷������������site_valueֵ
	bool runFlow(int time, bool addLog);										//���з�����
	void generateOutAnswer();							//���ɴ𰸲����
	void sortSiteValue(int siteID);
	bool updateBestAns();

	void updateLocalSiteValue(int time);
	void sortLocalSiteValue(int time);
	void setFlowGraphWithLocal(int limitFlow, int time, int currentCycle);

	void initSiteValueFromMaxFlow();
	void setMaxFlow(int limitFlow, int time);
	bool runMaxFlow(int time, bool addLog);
	void updateSiteValueFromMaxFlow();
		
	std::vector<int> lastBinaryAns;						//time, binary ans

	std::vector<std::vector<std::vector<std::pair<int, int>>>> bestLog;
	std::vector<std::vector<int>> bestSiteValue;
	std::vector<std::vector<int>> bestSiteValueSortRank;	
	std::vector<std::vector<int>> bestSiteValueTimeRank;
	int bestAns;



public:
	OptimizerMcmfPlanA(DataManager* _dataManager);
	int solve(int cycleCnt = 1, int binaryCnt = 5, double k = 0.5);
};